﻿//-------------------------------------------------------------------
//	Copyright (c) 2010-2014  Zhirnov Andrey
//	This file is part of the "UX Standard Lib" project.
//	See copyright notice in "UX_STL_Core.h".
//-------------------------------------------------------------------

#ifndef _UXS_ALGORITMS_H
#define _UXS_ALGORITMS_H

#pragma once

#include "TArray.h"

namespace UX_STL
{
namespace UXTypes
{
	
/*
=================================================
	обход всех элементов колекции
=================================================
*/
	template <typename T, typename U>
	inline void ForEach(T tBegin, T tEnd, U &tFunc)
	{
		while ( tBegin < tEnd )
		{
			tFunc( *tBegin );
			++tBegin;
		}
	}


	template <typename T, typename U>
	inline void ForEach(T *pArray, usize uCount, U &tFunc)
	{
		ForEach<T*, U>( pArray, pArray + uCount, tFunc );
	}
	

	template <usize I, typename T, typename U>
	inline void ForEach(T (&tArr)[I], U &tFunc)
	{
		ForEach<T*, U>( tArr, tArr + I, tFunc );
	}


	template <typename T, typename U>
	inline void ForEach(T& sArr, U &tFunc)
	{
		ForEach( sArr.Begin(), sArr.End(), tFunc );
	}
	
/*
=================================================
	обход всех элементов колекции,
	с возможностью удаления элементов
=================================================
*/
	template <typename T, typename U>
	inline void ForEachD(T &sArray, U &tFunc)
	{
		usize	u_count = sArray.Count();

		for (usize i = 0; i < sArray.Count();)
		{
			tFunc( sArray[i] );

			if ( u_count == sArray.Count() )
				++i;
			else
				u_count = sArray.Count();
		}
	}



	//
	// Default Search Comparison
	//

	template <typename T>
	struct TSearchCmp
	{
		const T &	_tValue;
		///
		TSearchCmp(const T &tValue): _tValue(tValue) {}

		template <typename B>
		bool operator () (const B &tValue) const
		{
			return ( tValue == _tValue );
		}

		template <typename B>
		bool operator == (const B &tValue) const
		{
			return ( tValue == _tValue );
		}

		// for binary search
		template <typename B>
		bool operator < (const B &tValue) const
		{
			return ( _tValue < tValue );
		}

		template <typename B>
		bool operator > (const B &tValue) const
		{
			return ( _tValue > tValue );
		}
	};

/*
=================================================
	ищет до первого совпадения начиная с начала массива
=================================================
*/
	template <typename T, typename C>
	inline bool FindFirstC(T tBegin, T tEnd, T &tResult, C &sCmp)
	{
		while ( tBegin < tEnd )
		{
			if ( sCmp( *tBegin ) ) {
				tResult = tBegin;
				return true;
			}

			++tBegin;
		}
		return false;
	}

	template <typename T, typename B>
	inline bool FindFirst(T *pBegin, T *pEnd, const B &tValue, T *&pResult)
	{
		TSearchCmp<B>	s_cmp( tValue );
		return FindFirstC<T *>( pBegin, pEnd, pResult, s_cmp );
	}

	template <typename T, typename E, typename B>
	inline bool FindFirst(T &sArray, const E &tValue, B *&pResult)
	{
		typedef typename T::value_t *	P;

		TSearchCmp<E>	s_cmp( tValue );
		return FindFirstC< P, TSearchCmp<E> >( (P) sArray.Begin(), (P) sArray.End(), pResult, s_cmp );
	}

	template <usize I, typename T, typename B>
	inline bool FindFirst(T (&tArr)[I], const B &tValue, T *&pResult)
	{
		return FindFirst<T*>( tArr, tArr + I, tValue, pResult );
	}

/*
=================================================
	ищет до первого совпадения начиная с конца массива
=================================================
*/
	template <typename T, typename C>
	inline bool FindLastC(T tBegin, T tEnd, T &tResult, C &sCmp)
	{
		--tEnd;	// to last element

		while ( tBegin <= tEnd )
		{
			if ( sCmp( *tEnd ) ) {
				tResult = tEnd;
				return true;
			}

			--tEnd;
		}
		return false;
	}

	template <typename T, typename B>
	inline bool FindLast(T *pBegin, T *pEnd, const B &tValue, T *&pResult)
	{
		TSearchCmp<B>	s_cmp( tValue );
		return FindLastC( pBegin, pEnd, pResult, s_cmp );
	}

	template <typename T, typename E, typename B>
	inline bool FindLast(T &sArray, const E &tValue, B *&pResult)
	{
		return FindLast( sArray.Begin(), sArray.End(), tValue, pResult );
	}

	template <usize I, typename T, typename B>
	inline bool FindLast(T (&tArr)[I], const B &tValue, T *&pResult)
	{
		return FindLast( tArr, tArr + I, tValue, pResult );
	}

/*
=================================================
	записывает в массив все елементы прошедшие проверку
=================================================
*/
	template <typename T, typename A, typename C>
	inline bool FindAllC(T tBegin, T tEnd, A &aResult, C &sCmp)
	{
		--tEnd;	// to last element

		if ( IsOdd( (tEnd - tBegin)/sizeof(T)+1 ) )
		{
			if ( sCmp( *tEnd ) )
				aResult << tEnd;

			--tEnd;
		}


		while ( tBegin <= tEnd )
		{
			if ( sCmp( *tBegin ) )
				aResult << tBegin;

			if ( sCmp( *tEnd ) )
				aResult << tEnd;

			--tEnd;
			++tBegin;
		}
		return not aResult;
	}

	template <typename T, typename B>
	inline bool FindAll(T *pBegin, T *pEnd, const B &tValue, array< T *, TFastCopyStrategy<T *> > &aResult)
	{
		TSearchCmp<B>	s_cmp;
		return FindAllC( pBegin, pEnd, aResult, s_cmp );
	}

	template <typename T, typename E, typename R>
	inline bool FindAll(T &sArray, const E &tValue, array<R> &aResult)
	{
		return FindAll( sArray.Begin(), sArray.End(), tValue, aResult );
	}

	template <usize I, typename T, typename B>
	inline bool FindAll(T (&tArr)[I], const B &tValue, array< T *, TFastCopyStrategy<T *> > &aResult)
	{
		return FindAll( tArr, tArr + I, tValue, aResult );
	}
	
/*
=================================================
	ищет до первого совпадения
=================================================
*/
	template <typename T, typename C, typename B>
	inline bool FindAnyC(T tBegin, T tEnd, B &tResult, C &sCmp)
	{
		--tEnd;	// to last element

		if ( IsOdd( (tEnd - tBegin)/sizeof(T)+1 ) )
		{
			if ( sCmp( *tEnd ) ) {
				tResult = tEnd;
				return true;
			}

			--tEnd;
		}

		while ( tBegin < tEnd )
		{
			if ( sCmp( *tBegin ) ) {
				tResult = tBegin;
				return true;
			}

			if ( sCmp( *tEnd ) ) {
				tResult = tEnd;
				return true;
			}

			--tEnd;
			++tBegin;
		}

		return false;
	}

	template <typename T, typename B, typename R>
	inline bool FindAny(T *pBegin, T *pEnd, const B &tValue, R *&pResult)
	{
		TSearchCmp<B>	s_cmp( tValue );
		return FindAnyC( pBegin, pEnd, pResult, s_cmp );
	}

	template <typename T, typename E, typename B>
	inline bool FindAny(T &sArray, const E &tValue, B *&pResult)
	{
		return FindAny( sArray.Begin(), sArray.End(), tValue, pResult );
	}

	template <usize I, typename T, typename B>
	inline bool FindAny(T (&tArr)[I], const B &tValue, T *&pResult)
	{
		return FindAny( tArr, tArr + I, tValue, pResult );
	}
	
/*
=================================================
	двоичный поиск по отсортированному массиву
=================================================
*/
	template <typename T>
	inline T _ptr_add_div2(T a, T b)
	{
		return a + ( ((usize(b) - usize(a)) / sizeof(T)) >> 1 );
	}

	template <typename T, typename B, typename C>
	inline bool BinarySearchC(T left, T right, B& tResult, C &sCmp)
	{
		--right;	// to last element

		while ( right - left > 1 )
		{
			T	mid = _ptr_add_div2( left, right );

			if ( sCmp > *mid )
				left = mid;
			else
				right = mid;
		}

		for (usize i = 0; i < 2 and left <= right; ++i, ++left)
		{
			if ( sCmp == *left )
			{
				tResult = left;
				return true;
			}
		}

		return false;
	}

	template <typename T, typename B, typename R>
	inline bool BinarySearch(T *pBegin, T *pEnd, const B &tValue, R *&pResult)
	{
		TSearchCmp<B>	s_cmp( tValue );
		return BinarySearchC( pBegin, pEnd, pResult, s_cmp );
	}

	template <typename T, typename E, typename B>
	inline bool BinarySearch(T &sArray, const E &tValue, B *&pResult)
	{
		return BinarySearch( sArray.Begin(), sArray.End(), tValue, pResult );
	}

	template <usize I, typename T, typename B>
	inline bool BinarySearch(T (&tArr)[I], const B &tValue, T *&pResult)
	{
		return BinarySearch( tArr, tArr + I, tValue, pResult );
	}
	
/*
=================================================
	двоичный поиск по отсортированному массиву
	(используются индексы вместо итераторов)
=================================================
*/
	template <typename T, typename C>
	inline bool BinarySearchIndexC(const T &arr, usize &left, usize &right, usize &result, C &sCmp)
	{
		while ( right - left > 1 )
		{
			usize	mid = (left + right) >> 1;

			if ( sCmp > arr[mid] )
				left = mid;
			else
				right = mid;
		}

		for (usize i = 0; i < 2 and left+i <= right; ++i)
		{
			if ( sCmp == arr[left+i] )
			{
				result = left+i;
				return true;
			}
		}

		return false;
	}
	
	template <typename T, typename B>
	inline bool BinarySearchIndexC(const T &arr, usize &left, usize &right, const B &tValue, usize &result)
	{
		TSearchCmp<B>	s_cmp( tValue );
		return BinarySearchIndexC( arr, left, right, result, s_cmp );
	}

	template <typename T, typename B>
	inline bool BinarySearchIndex(const T *arr, usize size, const B &tValue, usize &result)
	{
		TSearchCmp<B>	s_cmp( tValue );
		usize			left = 0,
						right = size-1;
		return BinarySearchIndexC( arr, left, right, result, s_cmp );
	}

	template <typename T, typename B>
	inline bool BinarySearchIndex(const T &sArray, const B &tValue, usize &result)
	{
		TSearchCmp<B>	s_cmp( tValue );
		usize			left = 0,
						right = sArray.Count()-1;
		return BinarySearchIndexC( sArray, left, right, result, s_cmp );
	}

	template <usize I, typename T, typename B>
	inline bool BinarySearchIndex(T (&tArr)[I], const B &tValue, usize &result)
	{
		return BinarySearchIndex( tArr, tArr + I - 1, tValue, result );
	}


//-------------------------------------------------------------------

}	// UXTypes
}	// UX_STL

#endif	// _UXS_ALGORITMS_H